package org.hot100_3;

import java.util.List;

public class leetcode23 {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;

        for (int i = 0; i < lists.length; i++) {
            ans = merge(ans, lists[i]);
        }

        return ans;
    }

    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(-1);

        ListNode node = dummy;

        while (left != null && right != null) {
            if (left.val < right.val) {
                node.next = left;
                left = left.next;
            } else {
                node.next = right;
                right = right.next;
            }
            node = node.next;
        }

        if (left == null) {
            node.next = right;
        }

        if (right == null) {
            node.next = left;
        }


        return dummy.next;
    }
}
